package aco;

import java.util.ArrayList;


//蚁群类
public class Ants {

    // 蚂蚁类
    static class Ant {
        //for each of the m salesmen an ant will construct a tour, so that a candidate solution constructed by
        //an ant will be represented by a list of tours, one for each salesman
        // 并不是真的有蚂蚁在路径中行走，一个蚂蚁代表的是一个解（一个解中有多条路径，一个路径中有自己的城市序列）
        ArrayList<ArrayList<Integer>> tours;
        boolean[] visited; // 城市是否被访问的数组
        ArrayList<Double> tour_lengths; // 存储每条路径的长度的链表
        // contains the beginning of service for each customer, including the depot, taking into
        // account the opening time (beginning) of the time window,
        // the service time and the distance between customers

        // 开始服务的时间，开始为编号为索引的城市服务的时间
        double[] beginService;

        //current number of used vehicles (= number of routes/tours) for constructing a feasible solution
        //that serve all the customers' requests and satisfy the time windows and capacity constraints
        int usedVehicles;

        //stores for each partial tour/route under construction the current time
        //taking into account the beginning time of service for the last visited customer on the tour
        //存储每条路径的当前时间（每条路径中最后一个客户的开始服务时间）
        ArrayList<Double> currentTime;

        //used by the insertion heuristic when checking the feasibility of an insertion
        //it stores for every customer i already assigned to a route the earliest time
        // a delivery can be made at i
        // 规划的每条路径中，每个客户点的最早到达时间（在时间窗范围内）
        ArrayList<ArrayList<Double>> earliestTime;

        //used by the insertion heuristic when checking the feasibility of an insertion
        //it stores for every customer i already assigned to a route the latest time a delivery
        //can be made at i
        // 规划的每条路径中，每个客户点的最迟到达时间（在时间窗范围内）
        ArrayList<ArrayList<Double>> latestTime;

        //stores for each partial tour/route under construction the current quantity of goods
        //(given by the demand of each request) transported on the route
        ArrayList<Double> currentQuantity; // 每条路径的当前载量

        double total_tour_length; //总的路径长度
        double longest_tour_length; //最长的路径长度
        int indexLongestTour;  //the index of the longest tour

        //cities left to be visited by an ant (initially toVisit = n, which is the number of cities from the mTSP instance)
        int toVisit; // 还未访问的城市数量

        //stores the cost of each solution according to the considered objectives (2 in this case)
        double costObjectives[]; // 存储两个优化目标值

        //it is true if a new empty tour was added in the ant solution to service the remaining available
        //unrouted/unvisited customers（是否要添加新的车辆，增加新的路径）
        boolean addedEmptyTour;
    }

    public static final int MAX_ANTS = 1024;
    public static final int MAX_NEIGHBOURS = 512;

    // 公式计算中的权重
    public static final double weight1 = 0.4;  //0.3   //0.4
    public static final double weight2 = 0.4;  //0.5   //0.4
    public static final double weight3 = 0.2;  //0.2   //0.2

    //weight used in the nearest neighbour heuristic, when computing an initial solution to calculate the
    //value of the initial pheromone trail
    public static double initialWeight1;
    public static double initialWeight2;
    public static double initialWeight3;

    // it indicates that node at position/index i is committed if the value at position i is true;
    // the depot node is considered to be committed by default and it's not included in this array
    /* 保证了变量的可见性（visibility）。被volatile关键字修饰的变量，如果值发生了变更，其他线程立马可见，避免出现脏读的现象。 */
    // 存储城市锁定状态的集合，已经锁定的城市不能再更改
    public volatile static boolean[] committedNodes;

    //for each tour in T* (best so far solution) it indicates the position/index of the last node that was committed
    //public volatile static ArrayList<Integer> lastCommitted;

    static Ant ants[]; // 蚁群
    // volatile关键字，它能够使变量在值发生改变时能尽快地让其他线程知道
    public volatile static Ant best_so_far_ant; // 至今为止最好的蚂蚁
    static Ant restart_best_ant; // 当前蚁群的最优蚂蚁

    static double pheromone[][]; // 信息素矩阵
    //static double total[][];  //keeps heuristic information times pheromone for each arc

    static double prob_of_selection[][]; // 这个没用到

    static int n_ants; /* number of ants */

    /* length of nearest neighbor lists for the ants' solution construction */
    /* 表示为当前城市寻找邻近城市的数量 */
    static int nn_ants;

    static double rho; /* parameter for evaporation used in global pheromne update*/
    static double local_rho;  /* parameter for evaporation used in local pheromone update*/
    static double alpha; /* importance of trail */
    static double beta; /* importance of heuristic evaluate */
    static double q_0; /* probability of best choice in tour construction */

    static boolean as_flag; /* ant system */
    static boolean acs_flag; /* ant colony system (ACS) */

    static int u_gb; /* every u_gb iterations update with best-so-far ant */

    static double trail_0; /* initial pheromone level in ACS */


    static double HEURISTIC(int m, int n) {
        return (1.0 / (double) VRPTW.instance.distance[m][n]);
    }

    //  allocate the memory for the ant colony, the best-so-far ant
//	重置蚁群和局部最优蚂蚁
    static void allocate_ants(VRPTW instance) {
        int i, j;
        ants = new Ant[n_ants];

//		1. 将当前问题实例的所有请求城市都配置为未被锁定状态
        committedNodes = new boolean[VRPTW.n];
        for (i = 0; i < VRPTW.n; i++) {
            committedNodes[i] = false;
        }
        //lastCommitted = new ArrayList<Integer>();

//		2. 重置蚁群
        for (i = 0; i < n_ants; i++) {
            ants[i] = new Ant();
            ants[i].tours = new ArrayList();
            ants[i].tour_lengths = new ArrayList<Double>();
            ants[i].beginService = new double[VRPTW.n + 1];
            ants[i].currentTime = new ArrayList<Double>();
            ants[i].currentQuantity = new ArrayList<Double>();
            ants[i].usedVehicles = 1;
            ants[i].addedEmptyTour = false;
            for (j = 0; j < ants[i].usedVehicles; j++) {
                ants[i].tours.add(j, new ArrayList<Integer>());
                ants[i].tour_lengths.add(j, 0.0);
                //lastCommitted.add(j, 0);
            }
            ants[i].visited = new boolean[VRPTW.n];
            //the another node is the depot, which is by default visited by each salesman and added in its tour
            ants[i].toVisit = instance.getIdAvailableRequests().size();
            ants[i].costObjectives = new double[2];
            for (int indexObj = 0; indexObj < 2; indexObj++) {
                ants[i].costObjectives[indexObj] = 0;
            }
            ants[i].earliestTime = new ArrayList(ants[i].usedVehicles);
            ants[i].latestTime = new ArrayList(ants[i].usedVehicles);
        }

//		3. 重置全局最优蚂蚁
        best_so_far_ant = new Ant();
        best_so_far_ant.tours = new ArrayList();
        best_so_far_ant.tour_lengths = new ArrayList<Double>();
        best_so_far_ant.beginService = new double[VRPTW.n + 1];
        best_so_far_ant.currentTime = new ArrayList<Double>();
        best_so_far_ant.currentQuantity = new ArrayList<Double>();
        best_so_far_ant.usedVehicles = 1;
        best_so_far_ant.addedEmptyTour = false;
        for (j = 0; j < best_so_far_ant.usedVehicles; j++) {
            best_so_far_ant.tours.add(j, new ArrayList<Integer>());
            best_so_far_ant.tour_lengths.add(j, 0.0);
        }
        best_so_far_ant.visited = new boolean[VRPTW.n];
        //the another node is the depot, which is by default visited by each salesman and added in its tour
        best_so_far_ant.toVisit = instance.getIdAvailableRequests().size();
        best_so_far_ant.longest_tour_length = Double.MAX_VALUE;

        best_so_far_ant.costObjectives = new double[2];
        for (int indexObj = 0; indexObj < 2; indexObj++) {
            best_so_far_ant.costObjectives[indexObj] = 0;
        }
        best_so_far_ant.earliestTime = new ArrayList(best_so_far_ant.usedVehicles);
        best_so_far_ant.latestTime = new ArrayList(best_so_far_ant.usedVehicles);

//	    4. 重置局部最优蚂蚁
        restart_best_ant = new Ant();
        restart_best_ant.tours = new ArrayList();
        restart_best_ant.tour_lengths = new ArrayList<Double>();
        restart_best_ant.beginService = new double[VRPTW.n + 1];
        restart_best_ant.currentTime = new ArrayList<Double>();
        restart_best_ant.currentQuantity = new ArrayList<Double>();
        restart_best_ant.usedVehicles = 1;
        restart_best_ant.addedEmptyTour = false;
        for (j = 0; j < restart_best_ant.usedVehicles; j++) {
            restart_best_ant.tours.add(j, new ArrayList<Integer>());
            restart_best_ant.tour_lengths.add(j, 0.0);
        }
        restart_best_ant.visited = new boolean[VRPTW.n];
        //the another node is the depot, which is by default visited by each salesman and added in its tour
        restart_best_ant.toVisit = instance.getIdAvailableRequests().size();
        restart_best_ant.longest_tour_length = Double.MAX_VALUE;

        restart_best_ant.costObjectives = new double[2];
        for (int indexObj = 0; indexObj < 2; indexObj++) {
            restart_best_ant.costObjectives[indexObj] = 0;
        }
        restart_best_ant.earliestTime = new ArrayList(restart_best_ant.usedVehicles);
        restart_best_ant.latestTime = new ArrayList(restart_best_ant.usedVehicles);
	
		/*prob_of_selection = new double[ants[0].usedVehicles][nn_ants + 1];
		for (j = 0; j < ants[0].usedVehicles; j++) {
			for (i = 0; i < nn_ants; i++) {
			    prob_of_selection[j][i] = Double.POSITIVE_INFINITY;
			}
		}
		for (j = 0; j < (ants[0].usedVehicles - 1); j++) {
			prob_of_selection[j][nn_ants] = 0;
		}
		prob_of_selection[ants[0].usedVehicles - 1][nn_ants] = Double.POSITIVE_INFINITY;*/
    }

    //find the best ant of the current iteration（返回本次蚁群迭代的最优蚂蚁的编号）
    // (the one with the lowest number of used vehicles and with smaller total traveled distance)
    static int find_best() {
        double min1, min2;
        int k1, k2, k2_min;

//		1. 先根据车辆数量优先级比较
        //first detect the ant which uses the minimum number of vehicles
        min1 = ants[0].usedVehicles;
        for (k1 = 1; k1 < n_ants; k1++) {
            if (ants[k1].usedVehicles < min1) {
                min1 = ants[k1].usedVehicles;
            }
        }

//		2. 再根据总路程进行比较
        //among the vehicles which use the minimum number of vehicles, select the best ant as the one with the minimum total distance for its traveled tours
        min2 = Double.MAX_VALUE;
        k2_min = 0;
        for (k2 = 0; k2 < n_ants; k2++) {
            if (ants[k2].usedVehicles == min1) {
                if (ants[k2].total_tour_length < min2) {
                    min2 = ants[k2].total_tour_length;
                    k2_min = k2;
                }
            }
        }
        return k2_min;
    }

    /* Initialize pheromone trails */
    static void init_pheromone_trails(double initial_trail) {
        int i, j;
        for (i = 0; i < (VRPTW.n + 1); i++) {
            for (j = 0; j <= i; j++) {
                pheromone[i][j] = initial_trail;
                pheromone[j][i] = initial_trail;
				/*total[i][j] = initial_trail;
				total[j][i] = initial_trail;*/
            }
        }
    }

    // 更新可访问城市之间的信息素（普通更新，没有用到全局最优蚂蚁更新）
    // preserve some of the pheromone level on the edges between available nodes
    static void preservePheromones(VRPTW vrp) {
        for (int i = 0; i < (VRPTW.n + 1); i++) {
            for (int j = 0; j <= i; j++) {
                if (vrp.getIdAvailableRequests().contains(i - 1) && vrp.getIdAvailableRequests().contains(j - 1)
                        || ((i == 0) && vrp.getIdAvailableRequests().contains(j - 1))
                        || ((j == 0) && vrp.getIdAvailableRequests().contains(i - 1))) {
                    pheromone[i][j] = pheromone[i][j] * (1 - InOut.pheromonePreservation) + InOut.pheromonePreservation * trail_0;
                    pheromone[j][i] = pheromone[i][j];
                } else {
                    pheromone[i][j] = trail_0;
                    pheromone[j][i] = pheromone[i][j];
                }
            }
        }
    }

    // 全局信息素的衰减
    // implements the pheromone trail evaporation
    static void evaporation() {
        int i, j;
        for (i = 0; i < VRPTW.n + 1; i++) {
            for (j = 0; j <= i; j++) {
                pheromone[i][j] = (1 - rho) * pheromone[i][j];
                pheromone[j][i] = pheromone[i][j];
            }
        }
    }

    // 更新局部信息素（蚂蚁每向前走一步，则更新这一步的信息素）reinforces edges used in ant k's solution
    static void global_update_pheromone(Ant a) {
        int i, j, h, k, size;
        double d_tau;

        d_tau = 1.0 / (double) a.total_tour_length;
        for (i = 0; i < a.usedVehicles; i++) {
            size = a.tours.get(i).size();
            for (k = 0; k < size - 1; k++) {
                j = a.tours.get(i).get(k);
                h = a.tours.get(i).get(k + 1);

                j++;
                h++;

                pheromone[j][h] += d_tau;
                pheromone[h][j] = pheromone[j][h];
            }
        }
    }

    // calculates heuristic info times pheromone for each arc
   /* static void compute_total_information()
    {
		int i, j;
	
		for (i = 0; i < MTsp.n + 1; i++) {
		    for (j = 0; j < i; j++) {
				total[i][j] = Math.pow(pheromone[i][j], alpha) * Math.pow(HEURISTIC(i, j), beta);
				total[j][i] = total[i][j];
		    }
		}
    }*/

    //	清空蚂蚁的记录，重置蚂蚁
    // empty the ants's memory regarding visited cities
    static void ant_empty_memory(Ant a, VRPTW instance) {
        int i, j;

        a.total_tour_length = 0;
        a.longest_tour_length = Integer.MAX_VALUE;
        a.indexLongestTour = 0;
        a.addedEmptyTour = false;

        for (int indexObj = 0; indexObj < 2; indexObj++) {
            a.costObjectives[indexObj] = 0;
        }

        a.tour_lengths.clear();
        a.currentQuantity.clear();
        a.currentTime.clear();

        // clear all the elements (cities) from the tours of an ant
        for (i = 0; i < a.usedVehicles; i++) {
            a.tours.get(i).clear();
        }
        a.tours.clear();
        if (a.earliestTime != null) {
            a.earliestTime.clear();
        }
        if (a.latestTime != null) {
            a.latestTime.clear();
        }

        a.usedVehicles = 1;
        for (i = 0; i < a.usedVehicles; i++) {
            a.tour_lengths.add(i, 0.0);
            a.currentQuantity.add(i, 0.0);
            a.currentTime.add(i, 0.0);
            a.tours.add(i, new ArrayList<Integer>());
		   /* a.earliestTime.add(i, new ArrayList<Double>());
		    a.latestTime.add(i, new ArrayList<Double>());*/
        }

        for (j = 0; j < VRPTW.n; j++) {
            a.visited[j] = false;
        }
        for (j = 0; j < (VRPTW.n + 1); j++) {
            a.beginService[j] = 0;
        }
        //the another node is the depot, which is by default visited by each salesman and added in its tour
        a.toVisit = instance.getIdAvailableRequests().size();

    }

    //	复制蚂蚁a
    //create a copy of the ant a and return the created copy at the output
    static Ant copyAnt(Ant a) {

//    	1. first create an empty ant
        //TODO: copy also fields such as usedVehicle, current quantity, currentTime
        Ant copy = new Ant();
        copy.tours = new ArrayList(a.usedVehicles);
        copy.tour_lengths = new ArrayList<Double>(a.usedVehicles);
	    /*for (int j = 0; j < a.usedVehicles; j++) {
	    	copy.tours.add(j, new ArrayList<Integer>());
	    	copy.tour_lengths.add(j, 0.0);
	    }*/
        copy.visited = new boolean[VRPTW.n];
        copy.toVisit = VRPTW.n;

        copy.costObjectives = new double[2];
        //copy.weights = new double[TSP_ACO.k];

//	    2. then copy the information from the ant a
        copy.total_tour_length = a.total_tour_length;
        copy.usedVehicles = a.usedVehicles;
        for (int indexObj = 0; indexObj < 2; indexObj++) {
            copy.costObjectives[indexObj] = a.costObjectives[indexObj];
        }
        for (int i = 0; i < a.usedVehicles; i++) {
            copy.tour_lengths.add(i, a.tour_lengths.get(i));
            int size = a.tours.get(i).size();
            copy.tours.add(i, new ArrayList<Integer>(size));
            for (int j = 0; j < size; j++) {
                int elem = a.tours.get(i).get(j);
                copy.tours.get(i).add(elem);
            }
        }

        return copy;
    }

    //    返回未访问城市的链表（编号的集合）。
    //get the list with the unvisited customers
    static ArrayList unroutedCustomers(Ant a, VRPTW vrp) {

//    	1. 创建存储未访问城市的链表
        ArrayList<Integer> l = new ArrayList<Integer>(a.toVisit);

//    	2. 当前可访问城市编号的链表
        ArrayList<Integer> idKnownRequests = vrp.getIdAvailableRequests();
        int count = 0;

//    	3. 如果当前可访问城市编号的链表中，有城市未被访问，则放入未访问集合中
        //collect nodes missing from the ant's solution; depot is considered to be visisted by default
        for (int city : idKnownRequests) {
            if (a.visited[city] == false) {
                l.add(city);
                count++;
                if (count == a.toVisit) {
                    break;
                }
            }
        }
        return l;
    }

    //	为蚂蚁选择下一个城市，根据信息素重要性与启发式信息重要的乘积，作为评判标准。
//	如果当前已有路径末端可以插入请求城市，则在路径的末端加入请求城市；否则开启新路径
//	这个choose_best_next函数是只能把城市放在路径的尾端
//    这个方法中，查找的城市链表是所有未访问的城市链表（没经过排序，不是邻近城市集合）
    //choose for an ant as the next city the one with maximal value of heuristic information times pheromone
    static int[] choose_best_next(Ant a, VRPTW vrp) {
//    	0. 创建一些辅助变量
        int current_city, next_city, salesman = 0, indexTour, startIndex, startIndexTour = 0;
        double value_best = -1.;  /* values in total matrix are always >= 0.0 */
        double help;
        int[] values = new int[2];
        double distance, distanceDepot, arrivalTime, arrivalTimeDepot, beginService, beginServiceDepot;
        double currentTime = 0, timeDiference = 0, waitingTIme, waiting, deliveryUrgency, bestBeginService = 0;
        ArrayList<Request> reqList = vrp.getRequests();
        ArrayList<Integer> idKnownRequests = vrp.getIdAvailableRequests();
        ArrayList<Integer> lastCommitedIndexes;
        int pos;
        boolean appliedInsertion = false;

        // 初始化一个不可能的值，因为城市编号最大为 VRPTW.n-1；如果在下面操作后，此值没有变化，说明没有找到合适的路径，应该新建一条路径。
        next_city = VRPTW.n;

//		1. 判断上次操作是否添加了新的车辆路径处理当前的城市请求集合，确定开始查找的路径
        if (a.addedEmptyTour) {
            // 设置为最后一条路径（因为最后一条路径可能是上次查找新增的路径）
            startIndex = a.usedVehicles - 1;
        } else {
            // 从第一条路径开始遍历吧
            startIndex = 0;
        }

//		2. 尝试匹配每条路径和每个请求城市，找到最优的匹配方案：next_city, salesman, bestBeginService
        for (int indexSalesman = startIndex; indexSalesman < a.usedVehicles; indexSalesman++) {

//			2.1 遍历每条路径，获取当前路径中，最后访问城市的编号，作为当前城市current_city。
            int lastPos = a.tours.get(indexSalesman).size() - 1;
            current_city = a.tours.get(indexSalesman).get(lastPos);
            current_city++;

//			2.2 遍历请求城市的链表（城市编号的链表）。
            for (int city : idKnownRequests) {
                if (a.visited[city])
                    ; /* city already visited, do nothing */
                else {

//					2.2.1 计算，离开编号为current_city的城市后，开始为编号为city的城市服务的时间
                    distance = VRPTW.instance.distance[current_city][city + 1];
                    arrivalTime = a.currentTime.get(indexSalesman) + reqList.get(current_city).getServiceTime() + distance;
                    beginService = Math.max(arrivalTime, reqList.get(city + 1).getStartWindow());

//					2.2.2 计算，离开编号为city的城市后，开始为仓库服务的时间
                    distanceDepot = VRPTW.instance.distance[city + 1][0];
                    arrivalTimeDepot = beginService + reqList.get(city + 1).getServiceTime() + distanceDepot;
                    beginServiceDepot = Math.max(arrivalTimeDepot, reqList.get(0).getStartWindow());

//			    	2.2.3 判断将编号为city的城市，加入到蚂蚁a的，编号为indexSalesman的路径，是否可行。如果可行则计算help
                    if (VRPTW_ACS.isFeasible(vrp, a, city, beginService, beginServiceDepot, indexSalesman)) {
                        waiting = beginService - a.beginService[current_city] - reqList.get(current_city).getServiceTime() - distance;
                        // waitingTIme = Math.max(0.0, waiting);
				    	/*if (waitingTIme == 0) {
				    		waitingTIme = 0.05;
				    	}*/
                        // currentTime = a.currentTime.get(indexSalesman);
                        // if (currentTime == 0) {
                        currentTime = 0.001;
                        // }

//						2.2.3.1 计算编号city的城市配送的紧急性(Uij)
                        deliveryUrgency = reqList.get(city + 1).getEndWindow() - (a.beginService[current_city] + reqList.get(current_city).getServiceTime() + distance);
				    	/*if (deliveryUrgency == 0) {
				    		deliveryUrgency = 0.05;
				    	}*/

//						2.2.3.2 城市current_city的开始服务时间，到城市city的开始服务时间。（这之间的服务时间和路程时间）Tij
                        timeDiference = beginService - a.beginService[current_city] - reqList.get(current_city).getServiceTime();

                        //help = HEURISTIC(current_city, city + 1) * (1.0 / currentTime) * (1.0 / waitingTIme) * (1.0 / deliveryUrgency);
                        //help = HEURISTIC(current_city, city + 1) * (1.0 / waitingTIme) * (1.0 / deliveryUrgency);
				    	
				    	/*if (a.currentTime.get(indexSalesman) == 0 && reqList.get(city + 1).getStartWindow() == 0) {
				    		help = 1.0 / (weight1 * distance + weight2 * timeDiference);
				    	}
				    	else {
				    		help = 1.0 / (weight1 * distance + weight2 * timeDiference + weight3 * deliveryUrgency);
				    	}*/

//						2.2.3.3 计算当前城市current_city与下一个访问城市city的紧密程度help，越大越好
//						最终的help相当于(v, s)中概率之内的那个公式（上半个公式）
                        help = 1.0 / (weight1 * distance + weight2 * timeDiference + weight3 * deliveryUrgency); // （相当于计算mij的公式）
                        help = Math.pow(help, beta);
                        help = help * Math.pow(pheromone[current_city][city + 1], alpha);

//						2.2.3.4 如果当前的插入方式比之前更优秀，则更新三个重要变量
                        if (help > value_best) {
                            next_city = city;
                            value_best = help;
                            salesman = indexSalesman;
                            bestBeginService = beginService;
                        }
                    }

                }
            }
        }

//		3. 如果在已有路径中没有找到可行的（路径-城市），不能将未访问的城市加入到已有路径末尾
        //it means that not all the cities are covered and some customers has not yet been serviced
        //by using an insertion heuristic try to insert in the infeasible solution the customers not visited yet
        //when no more customer with feasible insertions can be found, start a new route/tour and add
        //one more vehicle for constructing a feasible solution
        if (next_city == VRPTW.n) {
            //System.out.println("Iter=" + InOut.iteration + ": Before insertion heuristic >> cities to be visited: " + a.toVisit);

//			3.1 如果未分配的城市请求数量不超过10个，可以使用插入启发式方法，将未访问城市插入到已有路径中
            if ((a.toVisit > 0) && (a.toVisit <= 10)) {

//				3.1.1 determine nodes that are not visited yet in the current ant's solution
                ArrayList<Integer> unroutedList = unroutedCustomers(a, vrp);
                if (appliedInsertion) {
                    startIndexTour = a.usedVehicles - 1;
                } else {
                    startIndexTour = 0;
                }

//				3.1.2 skip over committed (defined) nodes when performing insertion heuristic
                lastCommitedIndexes = new ArrayList<Integer>();
                for (int index = 0; index < Ants.best_so_far_ant.usedVehicles; index++) {
                    pos = Controller.getLastCommitedPos(index);
                    lastCommitedIndexes.add(pos);
                }

//				3.1.3 使用插入启发式方法
                InsertionHeuristic.insertUnroutedCustomers(a, vrp, unroutedList, startIndexTour, lastCommitedIndexes);
                appliedInsertion = true;
                //System.out.println("Iter=" + InOut.iteration + ": After insertion heuristic >> cities to be visited: " + a.toVisit);
            }

//			3.2 如果插入启发式操作之后，还有未分配的请求城市，则应该新建路径。
            //if no more unrouted customers can be feasible inserted in the solution and there are still
            //remaining unrouted customers, add a new tour
            if (a.toVisit > 0) {
                a.usedVehicles++;
                indexTour = a.usedVehicles - 1;
                a.tours.add(indexTour, new ArrayList<Integer>());
                a.tours.get(indexTour).add(-1);
                a.tour_lengths.add(indexTour, 0.0);
                a.currentQuantity.add(indexTour, 0.0);
                a.currentTime.add(indexTour, 0.0);

                a.addedEmptyTour = true;

                values[0] = -1;
                values[1] = indexTour;
            }

        }

//      4. 如果可以找到一个城市和路径的匹配
        else {
            a.tours.get(salesman).add(next_city);
            a.visited[next_city] = true;
            a.toVisit--;
            a.currentTime.set(salesman, bestBeginService);
            a.beginService[next_city + 1] = bestBeginService;
            double newQuantity = a.currentQuantity.get(salesman) + reqList.get(next_city + 1).getDemand();
            a.currentQuantity.set(salesman, newQuantity);

            values[0] = next_city;
            values[1] = salesman;
        }

        return values;
    }

    //    遍历蚂蚁a的每条路径，得到每条路径的末端城市的邻近城市集合，在此集合中找到一个最佳“路径-城市”匹配。
//    相比方法choose_best_next，本方法是在邻近城市集合中寻找，可能更加有效。
    //chooses for an ant as the next city the one with maximal value of heuristic information times pheromone
    static int[] neighbour_choose_best_next(Ant a, VRPTW vrp) {

//        0. 初始化参数
        int i, current_city, next_city, help_city, salesman = 0, startPos;
        double value_best = -1;  //values in total matrix are always >= 0.0
        double help;
        double distance, distanceDepot, arrivalTime, arrivalTimeDepot, beginService, beginServiceDepot;
        double currentTime = 0, timeDiference = 0, waitingTIme, waiting, deliveryUrgency, bestBeginService = 0;
        int[] values = new int[2];
        ArrayList<Request> reqList = vrp.getRequests();
        next_city = VRPTW.n;   //next_city = Integer.MAX_VALUE;

//        1. 设定开始遍历的位置
        if (a.addedEmptyTour) {
            startPos = a.usedVehicles - 1;
        } else {
            startPos = 0;
        }

//        2. 尝试匹配路径indexSalesman和城市help_city
        for (int indexSalesman = startPos; indexSalesman < a.usedVehicles; indexSalesman++) {

//            2.1 找到当前路径的末端城市，得到末端城市的临近访问城市
            int lastPos = a.tours.get(indexSalesman).size() - 1;
            current_city = a.tours.get(indexSalesman).get(lastPos);
            current_city++;

//            2.2 遍历在临近城市集合中每个城市(按照到current_city的距离,由小到大进行遍历)
            for (i = 0; i < nn_ants; i++) {

//                2.2.1 获取城市编号 help_city
                help_city = VRPTW.instance.nn_list[current_city][i];

//                2.2.2 如果城市help_city在可访问城市请求的集合中,且还未被访问过，则可以尝试计算help的值
                if ((vrp.getIdAvailableRequests().contains(help_city - 1)) && (!a.visited[help_city - 1])) {
                    distance = VRPTW.instance.distance[current_city][help_city];
                    arrivalTime = a.currentTime.get(indexSalesman) + reqList.get(current_city).getServiceTime() + distance;
                    beginService = Math.max(arrivalTime, reqList.get(help_city).getStartWindow());

                    distanceDepot = VRPTW.instance.distance[help_city][0];
                    arrivalTimeDepot = beginService + reqList.get(help_city).getServiceTime() + distanceDepot;
                    beginServiceDepot = Math.max(arrivalTimeDepot, reqList.get(0).getStartWindow());

//                    2.2.3 判断将城市help_city插入到路径indexSalesman是否可行?
                    if (VRPTW_ACS.isFeasible(vrp, a, help_city - 1, beginService, beginServiceDepot, indexSalesman)) {
                        waiting = beginService - a.beginService[current_city] - reqList.get(current_city).getServiceTime() - distance;
                        waitingTIme = Math.max(0.0, waiting);
			    		/*if (waiting <= 0) {
			    			waitingTIme = 0;
			    		}
			    		else {
			    			waitingTIme = waiting;
			    		}*/
				    	/*if (waitingTIme == 0) {
				    		waitingTIme = 0.05;
				    	}*/
                        currentTime = a.currentTime.get(indexSalesman);
                        if (currentTime == 0) {
                            currentTime = 0.001;
                        }

//                        2.2.4 计算当前城市current_city与下一个访问城市city的紧密程度help，越大越好
                        deliveryUrgency = reqList.get(help_city).getEndWindow() - (a.beginService[current_city] + reqList.get(current_city).getServiceTime() + distance);
				    	/*if (deliveryUrgency == 0) {
				    		deliveryUrgency = 0.05;
				    	}*/
                        timeDiference = beginService - a.beginService[current_city] - reqList.get(current_city).getServiceTime();

                        //help = HEURISTIC(current_city, help_city) * (1.0 / currentTime) * (1.0 / waitingTIme) * (1.0 / deliveryUrgency);
                        //help = HEURISTIC(current_city, help_city) * (1.0 / waitingTIme) * (1.0 / deliveryUrgency);
				    	
				    	/*if (a.currentTime.get(indexSalesman) == 0 && reqList.get(help_city).getStartWindow() == 0) {
				    		help = 1.0 / (weight1 * distance + weight2 * timeDiference);
				    	}
				    	else {
				    		help = 1.0 / (weight1 * distance + weight2 * timeDiference + weight3 * deliveryUrgency);
				    	}*/
                        help = 1.0 / (weight1 * distance + weight2 * timeDiference + weight3 * deliveryUrgency);
                        help = Math.pow(help, beta);
                        help = help * Math.pow(pheromone[current_city][help_city], alpha);

//                        2.2.5 如果较前一个匹配更优
                        if (help > value_best) {
                            value_best = help;
                            next_city = help_city - 1;
                            salesman = indexSalesman;
                            bestBeginService = beginService;
                        }
                    }
                }
            }
        }

//        3. 如果临近城市集合中的所有城市,都不能匹配到已有路径中
        if (next_city == VRPTW.n) {
            // all cities in nearest neighbor list were already visited
            // 用choose_best_next(a, vrp)方法再操作一遍（在更大范围内搜索一下）,顺便生成新的路径
            values = choose_best_next(a, vrp);
            return values;
        }
//        4. 如果邻近城市集合可以匹配到路径
        else {
            a.tours.get(salesman).add(next_city);
            a.visited[next_city] = true;
            a.toVisit--;
            a.currentTime.set(salesman, bestBeginService);
            a.beginService[next_city + 1] = bestBeginService;
            double newQuantity = a.currentQuantity.get(salesman) + reqList.get(next_city + 1).getDemand();
            a.currentQuantity.set(salesman, newQuantity);
            values[0] = next_city;
            values[1] = salesman;
            return values;
        }

    }

    //    尝试将城市加入到指定的路径末尾
//    从当前未访问的城市请求集合中匹配最佳的“路径-城市”，插入到indexSalesman路径末端。找不到则跳出。
    static void choose_closest_nn(Ant a, int indexSalesman, VRPTW vrp) {
        int current_city, next_city, indexTour;
        double distance, distanceDepot, arrivalTime, arrivalTimeDepot, beginService, beginServiceDepot;
        double timeDiference, deliveryUrgency, bestBeginService = 0, minValue, metricValue;
        ArrayList<Request> reqList = vrp.getRequests(); // 请求城市的集合
        ArrayList<Integer> idKnownRequests = vrp.getIdAvailableRequests(); // 请求中的城市编号集合

        while (a.toVisit > 0) {
            next_city = VRPTW.n;
            minValue = Integer.MAX_VALUE;

//			1. 路径indexSalesman的末端城市的编号
            int lastPos = a.tours.get(indexSalesman).size() - 1;
            current_city = a.tours.get(indexSalesman).get(lastPos);
            current_city++;

//			2. 找到合适的请求城市：next_city
            for (int city : idKnownRequests) {
                if (a.visited[city])
                    ;  //city already visited
                else {
                    distance = VRPTW.instance.distance[current_city][city + 1];
                    arrivalTime = a.currentTime.get(indexSalesman) + reqList.get(current_city).getServiceTime() + distance;
                    beginService = Math.max(arrivalTime, reqList.get(city + 1).getStartWindow());

                    distanceDepot = VRPTW.instance.distance[city + 1][0];
                    arrivalTimeDepot = beginService + reqList.get(city + 1).getServiceTime() + distanceDepot;
                    beginServiceDepot = Math.max(arrivalTimeDepot, reqList.get(0).getStartWindow());

                    if (VRPTW_ACS.isFeasible(vrp, a, city, beginService, beginServiceDepot, indexSalesman)) {
                        //compute the value of the "closeness" metric; this metric tries to account
                        //for both geographical and temporal closeness of customers
                        timeDiference = beginService - a.beginService[current_city] - reqList.get(current_city).getServiceTime();
                        deliveryUrgency = reqList.get(city + 1).getEndWindow() - (a.beginService[current_city] + reqList.get(current_city).getServiceTime() + distance);
			    		
			    		/*if (a.currentTime.get(indexSalesman) == 0 && reqList.get(city + 1).getStartWindow() == 0) {
			    			metricValue = weight1 * distance + weight2 * timeDiference;
				    	}
				    	else {
				    		metricValue = weight1 * distance + weight2 * timeDiference + weight3 * deliveryUrgency;
				    	}*/
                        //metricValue = 0.5 * distance + 0.3 * timeDiference + 0.2 * deliveryUrgency;
                        //metricValue = initialWeight1 * distance + initialWeight2 * timeDiference + initialWeight3 * deliveryUrgency;
                        metricValue = weight1 * distance + weight2 * timeDiference + weight3 * deliveryUrgency;

                        if (metricValue < minValue) {
                            next_city = city;
                            minValue = metricValue;
                            bestBeginService = beginService;
                        }
                    }
                }
            }

//			3. 如果可以找到next_city放入到路径中，则插入路径中；否则跳出此程序
            //no more nodes can be feasible added in the tour
            if (next_city == VRPTW.n) {
                break;
            } else {
                a.tours.get(indexSalesman).add(next_city);
                a.visited[next_city] = true;
                a.toVisit--;
                a.currentTime.set(indexSalesman, bestBeginService);
                a.beginService[next_city + 1] = bestBeginService;
                a.currentQuantity.set(indexSalesman, a.currentQuantity.get(indexSalesman) + reqList.get(next_city + 1).getDemand());
            }
        }
    }

    //    在请求城市集合中，寻找一个最佳的插入城市，插入到路径indexSalesman中
//    如果没有合适的请求城市,就新建一条路径,以备后面的插入启发式操作
//    choose_closest_nn方法中，如果找不到合适请求城市，就退出方法
//    这里就不加注释了，跟choose_closest_nn的代码区别不大
    static void choose_closest_next(Ant a, int indexSalesman, VRPTW vrp) {
        int current_city, next_city, indexTour;
        double distance, distanceDepot, arrivalTime, arrivalTimeDepot, beginService, beginServiceDepot;
        double timeDiference, deliveryUrgency, bestBeginService = 0, minValue, metricValue;
        ArrayList<Request> reqList = vrp.getRequests();
        ArrayList<Integer> idKnownRequests = vrp.getIdAvailableRequests();

        next_city = VRPTW.n;
        int lastPos = a.tours.get(indexSalesman).size() - 1;
        current_city = a.tours.get(indexSalesman).get(lastPos);
        current_city++;

        minValue = Integer.MAX_VALUE;
        for (int city : idKnownRequests) {
            if (a.visited[city])
                ;  //city already visited
            else {
                distance = VRPTW.instance.distance[current_city][city + 1];
                arrivalTime = a.currentTime.get(indexSalesman) + reqList.get(current_city).getServiceTime() + distance;
                beginService = Math.max(arrivalTime, reqList.get(city + 1).getStartWindow());

                distanceDepot = VRPTW.instance.distance[city + 1][0];
                arrivalTimeDepot = beginService + reqList.get(city + 1).getServiceTime() + distanceDepot;
                beginServiceDepot = Math.max(arrivalTimeDepot, reqList.get(0).getStartWindow());

                if (VRPTW_ACS.isFeasible(vrp, a, city, beginService, beginServiceDepot, indexSalesman)) {
                    //compute the value of the "closeness" metric; this metric tries to account
                    //for both geographical and temporal closeness of customers
                    timeDiference = beginService - a.beginService[current_city] - reqList.get(current_city).getServiceTime();
                    deliveryUrgency = reqList.get(city + 1).getEndWindow() - (a.beginService[current_city] + reqList.get(current_city).getServiceTime() + distance);
		    		
		    		/*if (a.currentTime.get(indexSalesman) == 0 && reqList.get(city + 1).getStartWindow() == 0) {
		    			metricValue = weight1 * distance + weight2 * timeDiference;
			    	}
			    	else {
			    		metricValue = weight1 * distance + weight2 * timeDiference + weight3 * deliveryUrgency;
			    	}*/
                    //metricValue = 0.5 * distance + 0.3 * timeDiference + 0.2 * deliveryUrgency;
                    //metricValue = initialWeight1 * distance + initialWeight2 * timeDiference + initialWeight3 * deliveryUrgency;
                    metricValue = weight1 * distance + weight2 * timeDiference + weight3 * deliveryUrgency;

                    if (metricValue < minValue) {
                        next_city = city;
                        minValue = metricValue;
                        bestBeginService = beginService;
                    }
                }
            }
        }
        //it means that not all the cities are covered and some customers has not yet been serviced
        //by using insertion heuristic try to insert in the current tour of the solution under construction
        //the customers not visited yet
        //when no more customer with feasible insertions can be found, start a new route/tour and add
        //one more vehicle for constructing a feasible solution
        if (next_city == VRPTW.n) {
            //System.out.println("Cities to be visited: " + a.toVisit);

            //determine nodes that are not visited yet in the current tour
		    /*ArrayList<Integer> unroutedList = unroutedCustomers(a, vrp);	    
		    InsertionHeuristic.insertUnroutedCustomers(a, vrp, unroutedList, a.usedVehicles - 1, 1);*/

            //if no more unrouted customers can be feasible inserted in the solution and there are still
            //remaining unrouted customers, add a new tour
            if (a.toVisit > 0) {
                a.usedVehicles++;
                indexTour = a.usedVehicles - 1;
                a.tours.add(indexTour, new ArrayList<Integer>());
                a.tours.get(indexTour).add(-1);
                a.tour_lengths.add(indexTour, 0.0);
                a.currentQuantity.add(indexTour, 0.0);
                a.currentTime.add(indexTour, 0.0);
            }

        } else {
            a.tours.get(indexSalesman).add(next_city);
            a.visited[next_city] = true;
            a.toVisit--;
            a.currentTime.set(indexSalesman, bestBeginService);
            a.beginService[next_city + 1] = bestBeginService;
            a.currentQuantity.set(indexSalesman, a.currentQuantity.get(indexSalesman) + reqList.get(next_city + 1).getDemand());
        }
        System.out.println("车辆数："+a.usedVehicles);
    }

    //    计算（v, s）
//	根据概率在候选城市集合中,为当前蚂蚁选择当前城市的下一个城市
//	在蚂蚁a的候选邻近城市集合中，匹配到最佳的“路径-城市”组合。
    //Choose for an ant probabilistically a next city among all unvisited cities in the current city's candidate list
    static int[] neighbour_choose_and_move_to_next(Ant a, VRPTW vrp) {

//        0. 初始化参数值
        int i, j, help, city, salesman = 0;
        int current_city = 0;
        double rnd, partial_sum = 0., sum_prob = 0.0;
        double prob_ptr[][];
        double help1;
        int[] values = new int[2]; // 要返回的结果
        int[] tempCities = new int[a.usedVehicles];
        double distance, distanceDepot, arrivalTime, currentTime, arrivalTimeDepot, beginService, beginServiceDepot;
        double waitingTIme, waiting, deliveryUrgency, timeDiference = 0;
        ArrayList<Request> reqList = vrp.getRequests();

//        1. if rand(0, 1) < q_0
//        获取0~1的随机数，如果满足q_0条件，则在当前城市的邻近候选城市集合中，选择匹配“路径-城市”
        if ((q_0 > 0.0) && (Utilities.random01() < q_0)) {
            /*
             * with a probability q_0 make the best possible choice
             * according to pheromone trails and heuristic information, this corresponds to exploitation
             */
            /*
             * we first check whether q_0 > 0.0, to avoid the very common case
             * of q_0 = 0.0 to have to compute a random number, which is
             * expensive computationally
             */
            values = neighbour_choose_best_next(a, vrp);
            //values = choose_best_next(a, vrp);
            return values;
        }

//        2. otherwise
//        如果随机数不满足q_0条件。得到一个可能性概率分布的随机变量S，作为评价“路径-城市”匹配的标准
//          2.1 prob_ptr是矩阵，其中的值prob_ptr[current_city][i]代表城市current_city与距离他第i近的城市的紧密程度
//        每条路径的末端城市到邻近候选城市集合中，每个城市的距离。第二个索引包含仓库，所以要+1
//        假设矩阵中索引为nn_ants的城市代表的是仓库，或者其他重要的城市
        prob_ptr = new double[a.usedVehicles][nn_ants + 1];
        for (j = 0; j < a.usedVehicles; j++) {
            for (i = 0; i < nn_ants; i++) {
                prob_ptr[j][i] = Double.POSITIVE_INFINITY;
            }
        }

        // 已有路径的末端城市的路径距离为0
        for (j = 0; j < (a.usedVehicles - 1); j++) {
            prob_ptr[j][nn_ants] = 0; // 已经被访问的城市
        }

        // a.usedVehicles-1代表的路径是，新增的路径，里面只有仓库这一个城市点，回到自身的距离是正无穷
        prob_ptr[a.usedVehicles - 1][nn_ants] = Double.POSITIVE_INFINITY;

//          2.2 遍历路径集合，遍历候选邻近城市集合。
        for (int indexSalesman = 0; indexSalesman < a.usedVehicles; indexSalesman++) {

//            2.2.1 current_city city of Ant a in route indexSalesman
            /* current_city city of ant k */
            int lastPos = a.tours.get(indexSalesman).size() - 1;
            current_city = a.tours.get(indexSalesman).get(lastPos);
            current_city++;

//            2.2.2 遍历候选城市
            for (i = 0; i < nn_ants; i++) {
                city = VRPTW.instance.nn_list[current_city][i]; // 按照距离从小到大，取出城市编号
                // current_city ---> city
                distance = VRPTW.instance.distance[current_city][city];
                arrivalTime = a.currentTime.get(indexSalesman) + reqList.get(current_city).getServiceTime() + distance;
                beginService = Math.max(arrivalTime, reqList.get(city).getStartWindow());
                // city ---> depot
                distanceDepot = VRPTW.instance.distance[city][0];
                arrivalTimeDepot = beginService + reqList.get(city).getServiceTime() + distanceDepot;
                beginServiceDepot = Math.max(arrivalTimeDepot, reqList.get(0).getStartWindow());

//                1. 如果：不是可访问的请求城市，或者已经访问过该城市，或者不满足三个可行性条件
                if (!(vrp.getIdAvailableRequests().contains(city - 1)) || (a.visited[city - 1]) || (!VRPTW_ACS.isFeasible(vrp, a, city - 1, beginService, beginServiceDepot, indexSalesman)))
                    prob_ptr[indexSalesman][i] = 0.0; /* city already visited */
//                2. 如果同时满足：是可访问的请求城市，未访问过该城市，满足三个可行性条件
                else if ((VRPTW_ACS.isFeasible(vrp, a, city - 1, beginService, beginServiceDepot, indexSalesman)) && (vrp.getIdAvailableRequests().contains(city - 1)) && !(a.visited[city - 1])) {
//                    2.1其实计算等待时间根本没用
                    waiting = beginService - a.beginService[current_city] - reqList.get(current_city).getServiceTime() - distance;
                    waitingTIme = Math.max(0.0, waiting);
			    	/*if (waitingTIme == 0) {
			    		waitingTIme = 0.05;
			    	}*/
//                    2.2 计算当前城市current_city与接下来访问的城市city的紧密程度help1
                    deliveryUrgency = reqList.get(city).getEndWindow() - (a.beginService[current_city] + reqList.get(current_city).getServiceTime() + distance);

//                    currentTime = a.currentTime.get(indexSalesman);
//                    if (currentTime == 0) {
//                        currentTime = 0.001;
//                    }
                    timeDiference = beginService - a.beginService[current_city] - reqList.get(current_city).getServiceTime();

                    //help1 = HEURISTIC(current_city, city) *  (1.0 / currentTime) * (1.0 / waitingTIme) * (1.0 / deliveryUrgency);
                    //help1 = HEURISTIC(current_city, city) * (1.0 / waitingTIme) * (1.0 / deliveryUrgency);
			    	
			    	/*if (a.currentTime.get(indexSalesman) == 0 && reqList.get(city).getStartWindow() == 0) {
			    		help1 = 1.0 / (weight1 * distance + weight2 * timeDiference);
			    	}
			    	else {
			    		help1 = 1.0 / (weight1 * distance + weight2 * timeDiference + weight3 * deliveryUrgency);
			    	}*/
                    help1 = 1.0 / (weight1 * distance + weight2 * timeDiference + weight3 * deliveryUrgency);
                    help1 = Math.pow(help1, beta);
                    help1 = help1 * Math.pow(pheromone[current_city][city], alpha);
                    prob_ptr[indexSalesman][i] = help1; // 分子
                    tempCities[indexSalesman] = current_city; // 每条路径中当前城市的数组
                    sum_prob += prob_ptr[indexSalesman][i]; // 累计得到分母
                }
            }
        }

//        3. 如果所有的邻近候选城市集合都已经被访问过了，不只在候选邻近城市集合匹配最佳“路径-城市” 扩大范围，在请求城市集合中匹配最佳的“路径-城市”
        if (sum_prob <= 0.0) {
            /* All cities from the candidate  are tabu (are already visited) */
            values = choose_best_next(a, vrp);
            return values;
        }

//        4. 如果在邻近候选城市集合中可以找到至少一个合法城市，根据偏概率，选择一个匹配“路径-城市”
        else {
            /*
             * at least one neighbor is eligible, choose one according to the
             * selection probabilities
             */
            rnd = Utilities.random01();
            rnd *= sum_prob;
            i = 0;
            boolean done = false,// 是否匹配好“路径-城市”
                    forcedEnd = false;
            partial_sum = 0;

//            4.1 下面代码是为了找出一条路径salesman
            for (int indexSalesman = 0; indexSalesman < a.usedVehicles && !done; indexSalesman++) {
                i = 0;

//                4.1.1 计算partial_sum的值，patrial_sum是概率的偏和，对每条路径都找到一个最佳的“路径-城市”匹配
                partial_sum += prob_ptr[indexSalesman][i];
                /* This loop always stops because prob_ptr[nn_ants] == HUGE_VAL */
                while (partial_sum <= rnd) {
                    i++;
                    if (i < 0) {
                        System.out.println("Iter=" + InOut.iteration + " Test: indexSalesman= " + indexSalesman + " i= " + i);
                        partial_sum += Double.POSITIVE_INFINITY;
                        forcedEnd = true;
                        break;
                    }
                    if (i < prob_ptr[indexSalesman].length) {
                        //System.out.println("Test: indexSalesman= " + indexSalesman + " i= " + i);
                        partial_sum += prob_ptr[indexSalesman][i];
                        salesman = indexSalesman;
                    } else if (i >= prob_ptr[indexSalesman].length) {
                        break;
                    }
                    //add a big value to the partial_sum to be sure that the while loop ends
                    else if (indexSalesman == (a.usedVehicles - 1) && i >= prob_ptr[indexSalesman].length && partial_sum <= rnd) {
                        partial_sum += Double.POSITIVE_INFINITY;
                        forcedEnd = true;
                    }
                }

//                4.1.2 如果偏概率累积和在随机概率之外
                if (partial_sum > rnd) {
                    done = true;
                    if (!forcedEnd) {
                        salesman = indexSalesman;
                    } else { //choose randomly a salesman to whom add the city
                        salesman = (int) (Math.random() * a.usedVehicles);
                    }

                }

            }

//            4.2 如果找遍了候选邻近城市集合的所有城市，也没有为salesman路径找打合适的匹配城市，
//			      则应该换一种方法，寻找“路径-城市”的最佳匹配
            /*
             * This may very rarely happen because of rounding if rnd is close to 1.
             */
            if (i == nn_ants) {
                values = neighbour_choose_best_next(a, vrp);
                //values = choose_best_next(a, vrp);
                return values;
            }
            //System.out.println("nn_ants=" + nn_ants + " salesman=" + salesman + " i=" + i);
            current_city = tempCities[salesman];
            int maxIndex = 0;
            double maxValue = Double.MIN_VALUE;

//            4.3 i<0的时候，找到匹配最优路径salesman的最优城市节点manIndex，和最优匹配值maxValue
            if (i < 0) {
                maxValue = prob_ptr[salesman][0];
                for (j = 1; j < nn_ants; j++) {
                    if (prob_ptr[salesman][j] > maxValue) {
                        maxValue = prob_ptr[salesman][j];
                        maxIndex = j;
                    }
                }
                i = maxIndex;
            }

//            4.4 匹配路径salesman与城市help的操作
            help = VRPTW.instance.nn_list[current_city][i];

            distance = VRPTW.instance.distance[current_city][help];
            arrivalTime = a.currentTime.get(salesman) + reqList.get(current_city).getServiceTime() + distance;
            beginService = Math.max(arrivalTime, reqList.get(help).getStartWindow());

            a.tours.get(salesman).add(help - 1);
            a.visited[help - 1] = true;
            a.toVisit--;
            a.currentTime.set(salesman, beginService);
            a.beginService[help] = beginService;
            double newQuantity = a.currentQuantity.get(salesman) + reqList.get(help).getDemand();
            a.currentQuantity.set(salesman, newQuantity);

            values[0] = help - 1;
            values[1] = salesman;
            return values;
        }

    }

    //    根据蚂蚁a更新全局信息素（根据最优蚂蚁更新全局信息素）
    //reinforces the edges used in ant's solution as in ACS
    static void global_acs_pheromone_update(Ant a) {
        int i, j, h, k, size;
        double d_tau;

        d_tau = 1.0 / (double) a.total_tour_length;
        //d_tau = 1.0 / ((double) a.total_tour_length * (double) a.usedVehicles);
        //d_tau = 1.0 / ((double) a.total_tour_length * (double) a.usedVehicles * 0.1);
        //d_tau = 1.0 / ((double) a.total_tour_length + (double) a.usedVehicles * 0.01);
		/*double weightedSum = 0.5 * (double)a.total_tour_length + 0.5 * (double)a.usedVehicles;
		d_tau = 1.0 / Math.pow(weightedSum, 2.0);*/

        for (i = 0; i < a.usedVehicles; i++) {
            size = a.tours.get(i).size();
            for (k = 0; k < size - 1; k++) {
                j = a.tours.get(i).get(k);
                h = a.tours.get(i).get(k + 1);

                j++;
                h++;

                pheromone[j][h] = (1. - rho) * pheromone[j][h] + rho * d_tau;
                pheromone[h][j] = pheromone[j][h];
		
			    /*total[h][j] = Math.pow(pheromone[h][j], alpha) * Math.pow(HEURISTIC(h, j), beta);
			    total[j][h] = total[h][j];*/
            }
        }

    }

    //    局部更新信息素
//    更新蚂蚁指定路径最后一步的两个城市之间的信息素。
    //removes some pheromone on edge just passed by the ant
    static void local_acs_pheromone_update(Ant a, int indexSalesman) {
        int h, j;

        int lastPos = a.tours.get(indexSalesman).size() - 1;
        j = a.tours.get(indexSalesman).get(lastPos);
        h = a.tours.get(indexSalesman).get(lastPos - 1);

        j++;
        h++;

        /* still additional parameter has to be introduced */
        pheromone[h][j] = (1. - local_rho) * pheromone[h][j] + local_rho * trail_0;
        pheromone[j][h] = pheromone[h][j];
		/*total[h][j] = Math.pow(pheromone[h][j], alpha) * Math.pow(HEURISTIC(h, j), beta);
		total[j][h] = total[h][j];*/
    }

    //    复制蚂蚁a1到a2
    //copy solution from ant a1 into ant a2
    static void copy_from_to(Ant a1, Ant a2, VRPTW instance) {
        int i, j;

        Ants.ant_empty_memory(a2, instance);

        a2.total_tour_length = a1.total_tour_length;
		/*a2.longest_tour_length = a1.longest_tour_length;
		a2.indexLongestTour = a1.indexLongestTour;*/
        a2.toVisit = a1.toVisit;

        for (int indexObj = 0; indexObj < 2; indexObj++) {
            a2.costObjectives[indexObj] = a1.costObjectives[indexObj];
        }

        if (a2.usedVehicles < a1.usedVehicles) {
            for (int index = a2.usedVehicles; index < a1.usedVehicles; index++) {
                a2.tour_lengths.add(index, 0.0);
                a2.tours.add(index, new ArrayList<Integer>());
                a2.currentQuantity.add(index, 0.0);
                a2.currentTime.add(index, 0.0);
				/*a2.earliestTime.add(index, new ArrayList<Double>());
				a2.latestTime.add(index, new ArrayList<Double>());*/
            }
        }

        for (i = 0; i < a1.usedVehicles; i++) {
            a2.tour_lengths.set(i, a1.tour_lengths.get(i));
            a2.currentQuantity.set(i, a1.currentQuantity.get(i));
            a2.currentTime.set(i, a1.currentTime.get(i));
            int size = a1.tours.get(i).size();
            for (j = 0; j < size; j++) {
                int elem = a1.tours.get(i).get(j);
                a2.tours.get(i).add(elem);
            }

        }
        for (i = 0; i < VRPTW.n; i++) {
            a2.visited[i] = a1.visited[i];
        }
        a2.usedVehicles = a1.usedVehicles;

        for (i = 0; i < (VRPTW.n + 1); i++) {
            a2.beginService[i] = a1.beginService[i];
        }
    }

    //    计算蚂蚁a的，最长路径和最短路径的差值
    static double computeToursAmplitude(Ant a) {
        double min, max;
        int i;

        min = a.tour_lengths.get(0);
        max = a.tour_lengths.get(0);
        for (i = 1; i < a.tours.size(); i++) {
            if (a.tour_lengths.get(i) < min) {
                min = a.tour_lengths.get(i);
            }
            if (a.tour_lengths.get(i) > max) {
                max = a.tour_lengths.get(i);
            }
        }

        return (max - min);
    }

    //    初始化当前最优解
//    使用ants[0]蚂蚁苏苏，尝试将当前城市请求集合中的所有城市，都安排进蚂蚁ants[0]的路径中。输出总的路程长度。
//generate a nearest neighbor tour and compute tour length using only the available nodes (nodes known so far)
    static double nn_tour(VRPTW instance) {
        int step, salesman = 0;
        double sum = 0, sum1 = 0, scalledValue = 0, noVehicles = 1.0;

//        1. 清空蚂蚁信息
        ant_empty_memory(ants[0], instance);
        step = 0;

//        2. 为蚂蚁的每条路径设置出发仓库
        for (int i = 0; i < ants[0].usedVehicles; i++) {
            //place the ant on the depot city, which is the start city of each tour
            // -1 is a special marker for the deport city, so that it's not be confused with the rest of the cities
            // all the rest of the cities are represented by integer values > 0
            ants[0].tours.get(i).add(-1);
        }

//        3. 将可访问城市列表中的所有城市，都处理完。
//        如果现有路径不能访问城市，其中会生成新的路径，生成新的路径之后继续执行插入启发式。
        //there are still left available (known) cities to be visited
        while (ants[0].toVisit > 0) {
            salesman = ants[0].usedVehicles - 1;
            choose_closest_next(ants[0], salesman, instance);
        }

        //System.out.println("Cities to be visited: " + ants[0].toVisit);

//        4. 每条路径最终回到仓库
        int nrTours = ants[0].usedVehicles;
        for (int i = 0; i < nrTours; i++) {
            step = ants[0].tours.get(i).size();
            ants[0].tours.get(i).add(step, -1);
            ants[0].tour_lengths.set(i, VRPTW.compute_tour_length(ants[0].tours.get(i)));
            sum1 += ants[0].tour_lengths.get(i);
        }
        ants[0].total_tour_length = sum1;

//        5. 进行局部搜索，优化解
        if (VRPTW_ACS.ls_flag) {
            //ants[0] = VRPTW_ACS.local_search(ants[0], instance);
            ants[0] = VRPTW_ACS.relocateMultipleRouteIterated(ants[0], instance);
            ants[0] = VRPTW_ACS.exchangeMultipleRouteIterated(ants[0], instance);

            //compute new distances and update longest tour
            for (int l = 0; l < ants[0].usedVehicles; l++) {
                ants[0].tour_lengths.set(l, VRPTW.compute_tour_length(ants[0].tours.get(l)));
                sum += ants[0].tour_lengths.get(l);
            }
            ants[0].total_tour_length = sum;
        }
		
		/*for (int j = 0; j < ants[0].usedVehicles; j++) {
			lastCommitted.add(j, 0);  
		}*/

//        6. 存储最终结果
        //System.out.println("Initial (nearest neighbour tour) longest tour length: " + longestTourLength);
        double scalingValue = Controller.getScalingValue();
        if (scalingValue != 0) {
            scalledValue = ants[0].total_tour_length / scalingValue;
        }
        System.out.println("\nInitial (nearest neighbour tour) total tour length: " + ants[0].total_tour_length + " (scalled value = " + scalledValue + "); Number of vehicles used: " + ants[0].usedVehicles);
        sum1 = ants[0].total_tour_length;
        // noVehicles = ants[0].usedVehicles;
		
		/*for (int i = 0; i < nrTours; i++) {
			int tourLength = ants[0].tours.get(i).size();
			for (int j = 0; j < tourLength; j++) {
				int city = ants[0].tours.get(i).get(j);
				city = city + 1;  //so as to correspond to the city indexes from the VRPTW input file
				System.out.print(city + " ");		
			}
			System.out.println();
		}*/

        //initialize best solution so far with this solution constructed by the nearest neighbour heuristic
        Ants.copy_from_to(ants[0], Ants.best_so_far_ant, instance);
		
		/*for (int j = 0; j < Ants.best_so_far_ant.usedVehicles; j++) {
			lastCommitted.add(j, 0);  
		}*/

        //sum = ants[0].total_tour_length;
        ant_empty_memory(ants[0], instance);
        //return sum;
        //double value = sum1 * noVehicles;
        //double value = sum1 * ants[0].usedVehicles * 0.1;
        //double value = sum1 + ants[0].usedVehicles * 0.01;
		/*double weightedSum = 0.5 * (double)sum1 + 0.5 * (double)ants[0].usedVehicles;
		double value = Math.pow(weightedSum, 2.0);*/
        return sum1;
        //return value;
    }
}